/* ====================================================================
 * The Apache Software License, Version 1.1
 *
 * Copyright (c) 2002 The Apache Software Foundation.  All rights
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Apache" and "Apache Software Foundation" and
 *    "Apache POI" must not be used to endorse or promote products
 *    derived from this software without prior written permission. For
 *    written permission, please contact apache@apache.org.
 *
 * 5. Products derived from this software may not be called "Apache",
 *    "Apache POI", nor may "Apache" appear in their name, without
 *    prior written permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */


package org.apache.poi.hdf.extractor.util;

import java.util.*;


/*
 * A B-Tree like implementation of the java.util.Set inteface.  This is a modifiable set
 * and thus allows elements to be added and removed.  An instance of java.util.Comparator
 * must be provided at construction else all Objects added to the set must implement
 * java.util.Comparable and must be comparable to one another.  No duplicate elements
 * will be allowed in any BTreeSet in accordance with the specifications of the Set interface.
 * Any attempt to add a null element will result in an IllegalArgumentException being thrown.
 * The java.util.Iterator returned by the iterator method guarantees the elements returned
 * are in ascending order.  The Iterator.remove() method is supported.
 * Comment me
 *
 * @author Ryan Ackley 
 *
*/

public class BTreeSet extends AbstractSet implements Set {

    /*
     * Instance Variables
    */
    public BTreeNode root;
    private Comparator comparator = null;
    private int order;
    private int size = 0;

    /*
     *                             Constructors
     * A no-arg constructor is supported in accordance with the specifications of the
     * java.util.Collections interface.  If the order for the B-Tree is not specified
     * at construction it defaults to 32.
    */

    public BTreeSet() {
        this(6);           // Default order for a BTreeSet is 32
    }

    public BTreeSet(Collection c) {
        this(6);           // Default order for a BTreeSet is 32
        addAll(c);
    }

    public BTreeSet(int order) {
        this(order, null);
    }

    public BTreeSet(int order, Comparator comparator) {
        this.order = order;
        this.comparator = comparator;
        root = new BTreeNode(null);
    }


    /*
     * Public Methods
    */
    public boolean add(Object x) throws IllegalArgumentException {
        if (x == null) throw new IllegalArgumentException();
        return root.insert(x, -1);
    }

    public boolean contains(Object x) {
        return root.includes(x);
    }

    public boolean remove(Object x) {
        if (x == null) return false;
        return root.delete(x, -1);
    }

    public int size() {
        return size;
    }

    public void clear() {
        root = new BTreeNode(null);
        size = 0;
    }

    public java.util.Iterator iterator() {
        return new Iterator();
    }


    /*
     * Private methods
    */
    private int compare(Object x, Object y) {
        return (comparator == null ? ((Comparable)x).compareTo(y) : comparator.compare(x, y));
    }



    /*
     * Inner Classes
    */

    /*
     * Guarantees that the Objects are returned in ascending order.  Due to the volatile
     * structure of a B-Tree (many splits, steals and merges can happen in a single call to remove)
     * this Iterator does not attempt to track any concurrent changes that are happening to
     * it's BTreeSet.  Therefore, after every call to BTreeSet.remove or BTreeSet.add a new
     * Iterator should be constructed.  If no new Iterator is constructed than there is a
     * chance of receiving a NullPointerException. The Iterator.delete method is supported.
    */

    private class Iterator implements java.util.Iterator {
        private int index = 0;
        private Stack parentIndex = new Stack(); // Contains all parentIndicies for currentNode
        private Object lastReturned = null;
        private Object next;
        private BTreeNode currentNode;

        Iterator() {
            currentNode = firstNode();
            next = nextElement();
        }

        public boolean hasNext() {
            return next != null;
        }

        public Object next() {
            if (next == null) throw new NoSuchElementException();

            lastReturned = next;
            next = nextElement();
            return lastReturned;
        }

        public void remove() {
            if (lastReturned == null) throw new NoSuchElementException();

            BTreeSet.this.remove(lastReturned);
            lastReturned = null;
        }

        private BTreeNode firstNode() {
            BTreeNode temp = BTreeSet.this.root;

            while (temp.entries[0].child != null) {
                temp = temp.entries[0].child;
                parentIndex.push(new Integer(0));
            }

            return temp;
        }

        private Object nextElement() {
            if (currentNode.isLeaf()) {
                if (index < currentNode.nrElements) return currentNode.entries[index++].element;

                else if (!parentIndex.empty()) { //All elements have been returned, return successor of lastReturned if it exists
                    currentNode = currentNode.parent;
                    index = ((Integer)parentIndex.pop()).intValue();

                    while (index == currentNode.nrElements) {
                        if (parentIndex.empty()) break;
                        currentNode = currentNode.parent;
                        index = ((Integer)parentIndex.pop()).intValue();
                    }

                    if (index == currentNode.nrElements) return null; //Reached root and he has no more children
                    return currentNode.entries[index++].element;
                }

                else { //Your a leaf and the root
                    if (index == currentNode.nrElements) return null;
                    return currentNode.entries[index++].element;
                }
            }

            else { //Your not a leaf so simply find and return the successor of lastReturned
                currentNode = currentNode.entries[index].child;
                parentIndex.push(new Integer(index));

                while (currentNode.entries[0].child != null) {
                    currentNode = currentNode.entries[0].child;
                    parentIndex.push(new Integer(0));
                }

                index = 1;
                return currentNode.entries[0].element;
            }
        }
    }


    public static class Entry {

        public Object element;
        public BTreeNode child;
    }


    public class BTreeNode {

        public Entry[] entries;
        public BTreeNode parent;
        private int nrElements = 0;
        private final int MIN = (BTreeSet.this.order - 1) / 2;

        BTreeNode(BTreeNode parent) {
            this.parent = parent;
            entries = new Entry[BTreeSet.this.order];
            entries[0] = new Entry();
        }

        boolean insert(Object x, int parentIndex) {
            if (isFull()) { // If full, you must split and promote splitNode before inserting
                Object splitNode = entries[nrElements / 2].element;
                BTreeNode rightSibling = split();

                if (isRoot()) { // Grow a level
                    splitRoot(splitNode, this, rightSibling);
                    // Determine where to insert
                    if (BTreeSet.this.compare(x, BTreeSet.this.root.entries[0].element) < 0) insert(x, 0);
                    else rightSibling.insert(x, 1);
                }

                else { // Promote splitNode
                    parent.insertSplitNode(splitNode, this, rightSibling, parentIndex);
                    if (BTreeSet.this.compare(x, parent.entries[parentIndex].element) < 0) return insert(x, parentIndex);
                    else return rightSibling.insert(x, parentIndex + 1);
                }
            }

            else if (isLeaf()) { // If leaf, simply insert the non-duplicate element
                int insertAt = childToInsertAt(x, true);
                if (insertAt == -1) return false; // Determine if the element already exists
                else {
                    insertNewElement(x, insertAt);
                    BTreeSet.this.size++;
                    return true;
                }
            }

            else { // If not full and not leaf recursively find correct node to insert at
                int insertAt = childToInsertAt(x, true);
                return (insertAt == -1 ? false : entries[insertAt].child.insert(x, insertAt));
            }
            return false;
        }

        boolean includes(Object x) {
            int index = childToInsertAt(x, true);
            if (index == -1) return true;
            if (entries[index] == null || entries[index].child == null) return false;
            return entries[index].child.includes(x);
        }

        boolean delete(Object x, int parentIndex) {
            int i = childToInsertAt(x, true);
            int priorParentIndex = parentIndex;
            BTreeNode temp = this;
            if (i != -1) {
                do {
                    if (temp.entries[i] == null || temp.entries[i].child == null) return false;
                    temp = temp.entries[i].child;
                    priorParentIndex = parentIndex;
                    parentIndex = i;
                    i = temp.childToInsertAt(x, true);
                } while (i != -1);
            } // Now temp contains element to delete and temp's parentIndex is parentIndex

            if (temp.isLeaf()) { // If leaf and have more than MIN elements, simply delete
                if (temp.nrElements > MIN) {
                    temp.deleteElement(x);
                    BTreeSet.this.size--;
                    return true;
                }

                else { // If leaf and have less than MIN elements, than prepare the BTreeSet for deletion
                    temp.prepareForDeletion(parentIndex);
                    temp.deleteElement(x);
                    BTreeSet.this.size--;
                    temp.fixAfterDeletion(priorParentIndex);
                    return true;
                }
            }

            else { // Only delete at leaf so first switch with successor than delete
                temp.switchWithSuccessor(x);
                parentIndex = temp.childToInsertAt(x, false) + 1;
                return temp.entries[parentIndex].child.delete(x, parentIndex);
            }
        }


        private boolean isFull() { return nrElements == (BTreeSet.this.order - 1); }

        private boolean isLeaf() { return entries[0].child == null; }

        private boolean isRoot() { return parent == null; }

        /*
         * Splits a BTreeNode into two BTreeNodes, removing the splitNode from the
         * calling BTreeNode.
        */
        private BTreeNode split() {
            BTreeNode rightSibling = new BTreeNode(parent);
            int index = nrElements / 2;
            entries[index++].element = null;

            for (int i = 0, nr = nrElements; index <= nr; i++, index++) {
                rightSibling.entries[i] = entries[index];
                if (rightSibling.entries[i] != null && rightSibling.entries[i].child != null)
                    rightSibling.entries[i].child.parent = rightSibling;
                entries[index] = null;
                nrElements--;
                rightSibling.nrElements++;
            }

            rightSibling.nrElements--; // Need to correct for copying the last Entry which has a null element and a child
            return rightSibling;
        }

        /*
         * Creates a new BTreeSet.root which contains only the splitNode and pointers
         * to it's left and right child.
        */
        private void splitRoot(Object splitNode, BTreeNode left, BTreeNode right) {
            BTreeNode newRoot = new BTreeNode(null);
            newRoot.entries[0].element = splitNode;
            newRoot.entries[0].child = left;
            newRoot.entries[1] = new Entry();
            newRoot.entries[1].child = right;
            newRoot.nrElements = 1;
            left.parent = right.parent = newRoot;
            BTreeSet.this.root = newRoot;
        }

        private void insertSplitNode(Object splitNode, BTreeNode left, BTreeNode right, int insertAt) {
            for (int i = nrElements; i >= insertAt; i--) entries[i + 1] = entries[i];

            entries[insertAt] = new Entry();
            entries[insertAt].element = splitNode;
            entries[insertAt].child = left;
            entries[insertAt + 1].child = right;

            nrElements++;
        }

        private void insertNewElement(Object x, int insertAt) {

            for (int i = nrElements; i > insertAt; i--) entries[i] = entries[i - 1];

            entries[insertAt] = new Entry();
            entries[insertAt].element = x;

            nrElements++;
        }

        /*
         * Possibly a deceptive name for a pretty cool method.  Uses binary search
         * to determine the postion in entries[] in which to traverse to find the correct
         * BTreeNode in which to insert a new element.  If the element exists in the calling
         * BTreeNode than -1 is returned.  When the parameter position is true and the element
         * is present in the calling BTreeNode -1 is returned, if position is false and the
         * element is contained in the calling BTreeNode than the position of the element
         * in entries[] is returned.
        */
        private int childToInsertAt(Object x, boolean position) {
            int index = nrElements / 2;

            if (entries[index] == null || entries[index].element == null) return index;

            int lo = 0, hi = nrElements - 1;
            while (lo <= hi) {
                if (BTreeSet.this.compare(x, entries[index].element) > 0) {
                    lo = index + 1;
                    index = (hi + lo) / 2;
                }
                else {
                    hi = index - 1;
                    index = (hi + lo) / 2;
                }
            }

            hi++;
            if (entries[hi] == null || entries[hi].element == null) return hi;
            return (!position ? hi : BTreeSet.this.compare(x, entries[hi].element) == 0 ? -1 : hi);
        }


        private void deleteElement(Object x) {
            int index = childToInsertAt(x, false);
            for (; index < (nrElements - 1); index++) entries[index] = entries[index + 1];

            if (nrElements == 1) entries[index] = new Entry(); // This is root and it is empty
            else entries[index] = null;

            nrElements--;
        }

        private void prepareForDeletion(int parentIndex) {
            if (isRoot()) return; // Don't attempt to steal or merge if your the root

            // If not root then try to steal left
            else if (parentIndex != 0 && parent.entries[parentIndex - 1].child.nrElements > MIN) {
                stealLeft(parentIndex);
                return;
            }

            // If not root and can't steal left try to steal right
            else if (parentIndex < entries.length && parent.entries[parentIndex + 1] != null && parent.entries[parentIndex + 1].child != null && parent.entries[parentIndex + 1].child.nrElements > MIN) {
                    stealRight(parentIndex);
                    return;
            }

            // If not root and can't steal left or right then try to merge left
            else if (parentIndex != 0) {
                mergeLeft(parentIndex);
                return;
            }

            // If not root and can't steal left or right and can't merge left you must be able to merge right
            else mergeRight(parentIndex);
        }

        private void fixAfterDeletion(int parentIndex) {
            if (isRoot() || parent.isRoot()) return; // No fixing needed

            if (parent.nrElements < MIN) { // If parent lost it's n/2 element repair it
                BTreeNode temp = parent;
                temp.prepareForDeletion(parentIndex);
                if (temp.parent == null) return; // Root changed
                if (!temp.parent.isRoot() && temp.parent.nrElements < MIN) { // If need be recurse
                    BTreeNode x = temp.parent.parent;
                    int i = 0;
                    // Find parent's parentIndex
                    for (; i < entries.length; i++) if (x.entries[i].child == temp.parent) break;
                    temp.parent.fixAfterDeletion(i);
                }
            }
        }

        private void switchWithSuccessor(Object x) {
            int index = childToInsertAt(x, false);
            BTreeNode temp = entries[index + 1].child;
            while (temp.entries[0] != null && temp.entries[0].child != null) temp = temp.entries[0].child;
            Object successor = temp.entries[0].element;
            temp.entries[0].element = entries[index].element;
            entries[index].element = successor;
        }

        /*
         * This method is called only when the BTreeNode has the minimum number of elements,
         * has a leftSibling, and the leftSibling has more than the minimum number of elements.
        */
        private void stealLeft(int parentIndex) {
            BTreeNode p = parent;
            BTreeNode ls = parent.entries[parentIndex - 1].child;

            if (isLeaf()) { // When stealing from leaf to leaf don't worry about children
                int add = childToInsertAt(p.entries[parentIndex - 1].element, true);
                insertNewElement(p.entries[parentIndex - 1].element, add);
                p.entries[parentIndex - 1].element = ls.entries[ls.nrElements - 1].element;
                ls.entries[ls.nrElements - 1] = null;
                ls.nrElements--;
            }

            else { // Was called recursively to fix an undermanned parent
                entries[0].element = p.entries[parentIndex - 1].element;
                p.entries[parentIndex - 1].element = ls.entries[ls.nrElements - 1].element;
                entries[0].child = ls.entries[ls.nrElements].child;
                entries[0].child.parent = this;
                ls.entries[ls.nrElements] = null;
                ls.entries[ls.nrElements - 1].element = null;
                nrElements++;
                ls.nrElements--;
            }
        }

        /*
         * This method is called only when stealLeft can't be called, the BTreeNode
         * has the minimum number of elements, has a rightSibling, and the rightSibling
         * has more than the minimum number of elements.
        */
        private void stealRight(int parentIndex) {
            BTreeNode p = parent;
            BTreeNode rs = p.entries[parentIndex + 1].child;

            if (isLeaf()) { // When stealing from leaf to leaf don't worry about children
                entries[nrElements] = new Entry();
                entries[nrElements].element = p.entries[parentIndex].element;
                p.entries[parentIndex].element = rs.entries[0].element;
                for (int i = 0; i < rs.nrElements; i++) rs.entries[i] = rs.entries[i + 1];
                rs.entries[rs.nrElements - 1] = null;
                nrElements++;
                rs.nrElements--;
            }

            else { // Was called recursively to fix an undermanned parent
                for (int i = 0; i <= nrElements; i++) entries[i] = entries[i + 1];
                entries[nrElements].element = p.entries[parentIndex].element;
                p.entries[parentIndex].element = rs.entries[0].element;
                entries[nrElements + 1] = new Entry();
                entries[nrElements + 1].child = rs.entries[0].child;
                entries[nrElements + 1].child.parent = this;
                for (int i = 0; i <= rs.nrElements; i++) rs.entries[i] = rs.entries[i + 1];
                rs.entries[rs.nrElements] = null;
                nrElements++;
                rs.nrElements--;
            }
        }

        /*
         * This method is called only when stealLeft and stealRight could not be called,
         * the BTreeNode has the minimum number of elements, has a leftSibling, and the
         * leftSibling has more than the minimum number of elements.  If after completion
         * parent has fewer than the minimum number of elements than the parents entries[0]
         * slot is left empty in anticipation of a recursive call to stealLeft, stealRight,
         * mergeLeft, or mergeRight to fix the parent. All of the before-mentioned methods
         * expect the parent to be in such a condition.
        */
        private void mergeLeft(int parentIndex) {
            BTreeNode p = parent;
            BTreeNode ls = p.entries[parentIndex - 1].child;

            if (isLeaf()) { // Don't worry about children
                int add = childToInsertAt(p.entries[parentIndex - 1].element, true);
                insertNewElement(p.entries[parentIndex - 1].element, add); // Could have been a successor switch
                p.entries[parentIndex - 1].element = null;

                for (int i = nrElements - 1, nr = ls.nrElements; i >= 0; i--)
                    entries[i + nr] = entries[i];

                for (int i = ls.nrElements - 1; i >= 0; i--) {
                    entries[i] = ls.entries[i];
                    nrElements++;
                }

                if (p.nrElements == MIN && p != BTreeSet.this.root) {

                    for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x--, y--)
                        p.entries[x] = p.entries[y];
                    p.entries[0] = new Entry();
                    p.entries[0].child = ls; //So p doesn't think it's a leaf this will be deleted in the next recursive call
                }

                else {

                    for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
                        p.entries[x] = p.entries[y];
                    p.entries[p.nrElements] = null;
                }

                p.nrElements--;

                if (p.isRoot() && p.nrElements == 0) { // It's the root and it's empty
                    BTreeSet.this.root = this;
                    parent = null;
                }
            }

            else { // I'm not a leaf but fixing the tree structure
                entries[0].element = p.entries[parentIndex - 1].element;
                entries[0].child = ls.entries[ls.nrElements].child;
                nrElements++;

                for (int x = nrElements, nr = ls.nrElements; x >= 0; x--)
                    entries[x + nr] = entries[x];

                for (int x = ls.nrElements - 1; x >= 0; x--) {
                    entries[x] = ls.entries[x];
                    entries[x].child.parent = this;
                    nrElements++;
                }

                if (p.nrElements == MIN && p != BTreeSet.this.root) { // Push everything to the right
                    for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x++, y++){
                        System.out.println(x + " " + y);
                        p.entries[x] = p.entries[y];}
                    p.entries[0] = new Entry();
                }

                else { // Either p.nrElements > MIN or p == BTreeSet.this.root so push everything to the left
                    for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
                        p.entries[x] = p.entries[y];
                    p.entries[p.nrElements] = null;
                }

                p.nrElements--;

                if (p.isRoot() && p.nrElements == 0) { // p == BTreeSet.this.root and it's empty
                    BTreeSet.this.root = this;
                    parent = null;
                }
            }
        }

        /*
         * This method is called only when stealLeft, stealRight, and mergeLeft could not be called,
         * the BTreeNode has the minimum number of elements, has a rightSibling, and the
         * rightSibling has more than the minimum number of elements.  If after completion
         * parent has fewer than the minimum number of elements than the parents entries[0]
         * slot is left empty in anticipation of a recursive call to stealLeft, stealRight,
         * mergeLeft, or mergeRight to fix the parent. All of the before-mentioned methods
         * expect the parent to be in such a condition.
        */
        private void mergeRight(int parentIndex) {
            BTreeNode p = parent;
            BTreeNode rs = p.entries[parentIndex + 1].child;

            if (isLeaf()) { // Don't worry about children
                entries[nrElements] = new Entry();
                entries[nrElements].element = p.entries[parentIndex].element;
                nrElements++;
                for (int i = 0, nr = nrElements; i < rs.nrElements; i++, nr++) {
                    entries[nr] = rs.entries[i];
                    nrElements++;
                }
                p.entries[parentIndex].element = p.entries[parentIndex + 1].element;
                if (p.nrElements == MIN && p != BTreeSet.this.root) {
                    for (int x = parentIndex + 1, y = parentIndex; y >= 0; x--, y--)
                        p.entries[x] = p.entries[y];
                    p.entries[0] = new Entry();
                    p.entries[0].child = rs; // So it doesn't think it's a leaf, this child will be deleted in the next recursive call
                }

                else {
                    for (int x = parentIndex + 1, y = parentIndex + 2; y <= p.nrElements; x++, y++)
                        p.entries[x] = p.entries[y];
                    p.entries[p.nrElements] = null;
                }

                p.nrElements--;
                if (p.isRoot() && p.nrElements == 0) { // It's the root and it's empty
                    BTreeSet.this.root = this;
                    parent = null;
                }
           }

           else { // It's not a leaf

               entries[nrElements].element = p.entries[parentIndex].element;
               nrElements++;

               for (int x = nrElements + 1, y = 0; y <= rs.nrElements; x++, y++) {
                   entries[x] = rs.entries[y];
                   rs.entries[y].child.parent = this;
                   nrElements++;
               }
               nrElements--;

               p.entries[++parentIndex].child = this;

               if (p.nrElements == MIN && p != BTreeSet.this.root) {
                  for (int x = parentIndex - 1, y = parentIndex - 2; y >= 0; x--, y--)
                      p.entries[x] = p.entries[y];
                  p.entries[0] = new Entry();
               }

               else {
                   for (int x = parentIndex - 1, y = parentIndex; y <= p.nrElements; x++, y++)
                       p.entries[x] = p.entries[y];
                   p.entries[p.nrElements] = null;
               }

               p.nrElements--;

               if (p.isRoot() && p.nrElements == 0) { // It's the root and it's empty
                   BTreeSet.this.root = this;
                   parent = null;
               }
            }
        }
  }
}

